package code.mySpecializedTraining;

import java.util.*;

/**
 * @author 26029
 * @date 2025/4/21
 * @description
 */
public class Array {
    // 80. 删除有序数组中的重复项 II
    public int removeDuplicates(int[] nums) {
        // 1 <= nums.length <= 3 * 104
        int len = nums.length;
        int sameCount = 1;
        int replacePos = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] == nums[i - 1])
                sameCount++;
            else
                sameCount = 1;

            if (sameCount < 3) {
                nums[replacePos] = nums[i];
                replacePos++;
            }
        }
        return replacePos;
    }

    // 189. 轮转数组
    public void rotate(int[] nums, int k) {
        // 原地算法，翻转三次
        // 1 2 3 4 5 6 7 8 9  ↓  k = 3
        // 9 8 7 6 5 4 3 2 1  ↓
        // 7 8 9 6 5 4 3 2 1  ↓
        // 7 8 9 1 2 3 4 5 6
        int len = nums.length;
        k = k % len;
        reverseNums(nums, 0, len - 1);
        reverseNums(nums, 0, k - 1);
        reverseNums(nums, k, len - 1);
    }

    private void reverseNums(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    // 13. 罗马数字转整数
    public int romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        // 1 <= s.length <= 15
        int len = s.length();
        int ans = map.get(s.charAt(len - 1));
        int lastVal = ans;
        for (int i = len - 2; i >= 0; i--) {
            int nowVal = map.get(s.charAt(i));
            if (nowVal < lastVal)
                ans -= nowVal;
            else
                ans += nowVal;
            lastVal = nowVal;
        }
        return ans;
    }

    // 12. 整数转罗马数字
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }

    // 151. 反转字符串中的单词
    public String reverseWords(String s) {
        // 去掉首位空格
        char[] charArray = s.trim().toCharArray();
        // 去掉中间空格
        StringBuilder sb1 = new StringBuilder();
        for (int i = 0; i < charArray.length; i++) {
            // 如果不是第一个空格，跳过
            if (i > 0 && charArray[i] == ' ' && charArray[i - 1] == ' ')
                continue;
            sb1.append(charArray[i]);
        }
        // 放到数组里
        String[] split = sb1.toString().split(" ");
        StringBuilder sb2 = new StringBuilder();
        for (int i = split.length - 1; i >= 0 ;i--) {
            sb2.append(split[i]);
            if (i != 0)
                sb2.append(" ");
        }

        return sb2.toString();
    }

    // 68. 文本左右对齐
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> stringList = new ArrayList<>();
        // 遍历所有单词
        List<String> lineSelectedWord = new ArrayList<>();
        StringBuilder sb;
        int totalWordLen = 0;
        int totalWordNum = 0;
        for(String word : words) {
            int nowWordLen = word.length();
            // 如果加进来不够了，处理目前加进来的单词，清空
            if (nowWordLen + totalWordLen + totalWordNum > maxWidth) {
                sb = new StringBuilder();
                // 如果多于一个单词
                if (totalWordNum > 1) {
                    int leftSpaceNum = maxWidth - totalWordLen; // 5
                    int needSpacesNum = totalWordNum - 1; // 3
                    int baseSpaceNum = leftSpaceNum / needSpacesNum;
                    int moreSpaceNum = leftSpaceNum % needSpacesNum;
                    for (int i = 0; i < totalWordNum; i++) {
                        sb.append(lineSelectedWord.get(i));
                        if (i != totalWordNum - 1) {
                            sb.append(" ".repeat(baseSpaceNum));
                            if (moreSpaceNum > 0) {
                                sb.append(' ');
                                moreSpaceNum--;
                            }
                        }
                    }
                }
                // 如果只有一个单词
                else {
                    int rightSpaceNum = maxWidth - totalWordLen;
                    sb.append(lineSelectedWord.get(0));
                    sb.append(" ".repeat(rightSpaceNum));
                }
                stringList.add(sb.toString());
                totalWordLen = 0;
                totalWordNum = 0;
                lineSelectedWord.clear();
            }
            // 加上现在的单词
            totalWordLen += nowWordLen;
            totalWordNum ++;
            lineSelectedWord.add(word);
        }
        // 处理最后一行
        sb = new StringBuilder();
        int rightSpaceNum = maxWidth - totalWordLen - (totalWordNum - 1);
        for (int i = 0; i < totalWordNum; i++) {
            sb.append(lineSelectedWord.get(i));
            if (i != totalWordNum - 1) {
                sb.append(' ');
            }
        }
        sb.append(" ".repeat(rightSpaceNum));
        stringList.add(sb.toString());

        return stringList;
    }

    // 15. 三数之和
    public List<List<Integer>> threeSum_map(int[] nums) {
        // map法，有额外空间Map开销，也较慢 O(n^2)
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < len; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            for (int j = i + 1; j < len; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1])
                    continue;
                int nowTarget = - nums[i] - nums[j];
                if (map.containsKey(nowTarget) && map.get(nowTarget) > j) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[map.get(nowTarget)]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }

    public List<List<Integer>> threeSum_d(int[] nums) {
        // 双指针法，较快 O(n^2)
        int len = nums.length;
        List<List<Integer>> lists = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < len - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int target = -nums[i];
            int left = i + 1, right = len - 1;
            while (left < right) {
                if (nums[left] + nums[right] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                } else if (nums[left] + nums[right] > target) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return lists;
    }

    public static void main(String[] args) {
        Array aa = new Array();
        System.out.println(aa.fullJustify(new String[]{"", ""}, 3));
    }
}
